Network virtualization allows one or more specified networks to be implemented on a substrate network infrastructure. That is, a number of virtual networks may be specified and implemented on a physical network infrastructure. Virtual network embedding provides a mapping between the virtual nodes and virtual links of the virtual network to the physical nodes and physical links or paths of the physical substrate network. In addition to satisfying the virtual node and virtual link requirements, the mapping may also attempt to optimize, or satisfy, other constraints.
Virtual network embedding allows a plurality of virtual nodes and virtual links to be implemented in available physical resources. However, it is possible that the virtual network embedding results in a mapping that leaves the virtual network vulnerable to disconnection as a result of a physical link failure, which would render the virtual network, or a portion of the virtual network, unusable. The defined virtual network may experience connectivity issues due to the failure of a physical link. While it is possible to determine a mapping that maintains connectivity between virtual nodes in the event of a single physical link failure, the problem increases in complexity quickly as more link-failure resilience is desired and the number of virtual nodes is increased, particularly when other criteria are taken into account, such as efficient use of physical network resources.
It is desirable to provide a virtual network embedding technique capable of providing a mapping that can maintain virtual network connectivity in the event of multiple physical link failures.